/************************************************************************
                                                                     
   Xceed Ultimate ListBox for Silverlight                                                                                                                                            
   Copyright (C) 2010 Xceed Software Inc.    
                                                                     
   This program is provided to you under the terms of the GNU General Public  
   License version 2 as published by the Free Software Foundation. 
        
   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY, without even the implied warranty of 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License along 
   with this program, if not, write to the Free Software Foundation, Inc., 
   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

   This program can be provided to you by Xceed Software Inc. under a
   proprietary commercial license agreement for use in non-Open Source
   projects. Visit Xceed.com to find the commercial edition of 
   Xceed Ultimate ListBox for Silverlight.                                    
                                                                      
 **********************************************************************/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;

using Expr = System.Linq.Expressions.Expression;

namespace Xceed.Silverlight.Data
{
  internal sealed class LinqExpressionBuilder : FilterExpressionVisitor
  {
    #region Static Fields

    private static readonly Expression TrueExpression = null;

    // Here is the comparison expression that will filter out 
    // every item (1 != 1). A comparison expression is used 
    // since some data sources do not accept boolean values.
    private static readonly Expression FalseExpression = Expr.NotEqual(
                                                           Expr.Constant( 1 ),
                                                           Expr.Constant( 1 ) );

    #endregion

    #region Constructor

    internal LinqExpressionBuilder(
      FilterExpressionBase expression,
      ParameterExpression parameter,
      Func<ParameterExpression, string, Expression> getItemMemberValue,
      Func<string, Type> getItemMemberType )
    {
      if( parameter == null )
        throw new ArgumentNullException( "parameter" );

      if( getItemMemberValue == null )
        throw new ArgumentNullException( "getItemMemberValue" );

      m_parameter = parameter;
      m_getItemMemberValue = getItemMemberValue;
      m_preProcessor = new FilterExpressionPreProcessor( expression, getItemMemberType );
    }

    #endregion

    protected override void Initialize()
    {
      m_result = null;

      base.Initialize();
    }

    protected override FilterExpressionBase GetFirstExpression()
    {
      m_preProcessorResult = m_preProcessor.GetResult();

      return m_preProcessorResult.Expression;
    }

    protected internal override void Visit( FilterExpression expression )
    {

      object value = expression.Value;
      Type valueType = ( value != null ) ? value.GetType() : null;
      FilterOperator op = expression.FilterOperator;

      if( value == null )
      {
        m_result = this.HandleNullValue( expression );
      }
      else if( typeof( bool ).IsAssignableFrom( valueType ) )
      {
        m_result = this.HandleBooleanValue( expression );
      }
      else if( typeof( IComparable ).IsAssignableFrom( valueType ) )
      {
        m_result = this.HandleComparableValue( expression );
      }
      else if( ( op == FilterOperator.Equal ) || ( op == FilterOperator.NotEqual ) )
      {
        m_result = this.HandleEquatableValue( expression );
      }
      else
      {
        throw new InvalidOperationException( "An attempt was made to use an unsupported filter expression." );
      }
    }

    protected internal override void Visit( AndFilterExpression expression )
    {
      List<Expression> operands = new List<Expression>();

      foreach( FilterExpressionBase childExpression in expression.ChildExpressions )
      {
        this.Visit( childExpression );

        // Retrieve the value of the current operand.
        Expression operand = m_result;

        // An operand that returns false makes the and-expression totally useless.
        if( operand == LinqExpressionBuilder.FalseExpression )
        {
          m_result = operand;
          return;
        }

        // An operand that returns true shouldn't be consider since it doesn't bring
        // anything new to the and-expression.
        if( ( operand != null ) && ( operand != LinqExpressionBuilder.TrueExpression ) )
        {
          operands.Add( operand );
        }
      }

      // Set the new result.
      m_result = LinqExpressionBuilder.BalanceExpressionTree( operands, Expr.AndAlso );
    }

    protected internal override void Visit( OrFilterExpression expression )
    {
      List<Expression> operands = new List<Expression>();

      foreach( FilterExpressionBase childExpression in expression.ChildExpressions )
      {
        this.Visit( childExpression );

        // Retrieve the value of the current operand.
        Expression operand = m_result;

        // An operand that returns true makes the or-expression totally useless.
        if( operand == LinqExpressionBuilder.TrueExpression )
        {
          m_result = operand;
          return;
        }

        // An operand that returns false shouldn't be consider since it doesn't bring
        // anything new to the or-expression.
        if( ( operand != null ) && ( operand != LinqExpressionBuilder.FalseExpression ) )
        {
          operands.Add( operand );
        }
      }

      // Set the new result.
      m_result = LinqExpressionBuilder.BalanceExpressionTree( operands, Expr.OrElse );
    }

    protected internal override void Visit( NotFilterExpression expression )
    {
      this.Visit( expression.ChildExpression );

      // Retrieve the result of the visited nodes.
      Expression result = m_result;

      if( result == LinqExpressionBuilder.TrueExpression )
      {
        result = LinqExpressionBuilder.FalseExpression;
      }
      else if( result == LinqExpressionBuilder.FalseExpression )
      {
        result = LinqExpressionBuilder.TrueExpression;
      }
      else if( result != null )
      {
        result = Expr.Not( result );
      }

      // Set the new result.
      m_result = result;
    }

    internal Expression GetExpression()
    {
      this.Visit();

      if( m_result == null )
      {
        if( m_preProcessorResult.Target == PreProcessResult.TargetAll )
          return LinqExpressionBuilder.TrueExpression;

        if( m_preProcessorResult.Target == PreProcessResult.TargetNone )
          return LinqExpressionBuilder.FalseExpression;
      }

      return m_result;
    }

    private static Expression BalanceExpressionTree(
      IEnumerable<Expression> expressions,
      Func<Expression, Expression, Expression> combiner )
    {
      if( combiner == null )
        throw new ArgumentNullException( "combiner" );

      // Make sure there is at least one expression to balance.
      if( ( expressions == null ) || ( !expressions.Any() ) )
        return null;

      Queue<Expression> operands = new Queue<Expression>( expressions );
      if( operands.Count > 1 )
      {
        // Since we're combining the expression in pairs, we only need a resulting queue
        // half the size of the original one.
        Queue<Expression> results = new Queue<Expression>( ( operands.Count + 1 ) / 2 );

        // We need to combine nodes until we get a root node.
        while( operands.Count > 1 )
        {
          // Create the intermediate nodes from the child nodes.
          while( operands.Count > 0 )
          {
            // Get an expression that will be on the left side.
            Expression operand = operands.Dequeue();

            // There is at least one expression we can put on the right side.
            if( operands.Count > 0 )
            {
              // Create an intermediate node from the two expressions.
              operand = combiner.Invoke( operand, operands.Dequeue() );
            }

            // Put the intermediate node in a queue for the next iteration.
            results.Enqueue( operand );
          }

          // Now that we have combine the nodes of a level, we'll combine
          // the new resulting nodes until we get only one node, the root.
          Queue<Expression> swap = operands;
          operands = results;
          results = swap;
        }
      }

      return operands.Dequeue();
    }

    private Expression HandleNullValue( FilterExpression expression )
    {
      Expr memberValue = this.GetItemMemberValue( expression.MemberName );

      if( memberValue.Type.IsNullableType() )
      {
        FilterOperator op = expression.FilterOperator;

        if( op == FilterOperator.Equal )
          return LinqExpressionBuilder.CompareEqualNull( memberValue );

        if( op == FilterOperator.NotEqual )
          return LinqExpressionBuilder.CompareNotEqualNull( memberValue );
      }

      throw new InvalidOperationException( "An attempt was made to use an unsupported filter expression." );
    }

    private Expression HandleBooleanValue( FilterExpression expression )
    {
      return this.HandleEquatableValue( expression );
    }

    private Expression HandleComparableValue( FilterExpression expression )
    {
      Expr memberValue = this.GetItemMemberValue( expression.MemberName );
      ConstantExpression constant = Expr.Constant( expression.Value );
      FilterOperator op = expression.FilterOperator;
      bool isCaseSensitive = expression.IsCaseSensitive.GetValueOrDefault( true );

      return LinqExpressionBuilder.Compare( memberValue, constant, op, isCaseSensitive );
    }

    private Expression HandleEquatableValue( FilterExpression expression )
    {
      Expr memberValue = this.GetItemMemberValue( expression.MemberName );
      ConstantExpression constant = Expr.Constant( expression.Value );
      FilterOperator op = expression.FilterOperator;

      if( op == FilterOperator.Equal )
      {
        return LinqExpressionBuilder.CompareEqual( memberValue, constant );
      }
      else if( op == FilterOperator.NotEqual )
      {
        return LinqExpressionBuilder.CompareNotEqual( memberValue, constant );
      }

      throw new InvalidOperationException( "An attempt was made to use an unsupported filter expression." );
    }

    private static Expression Compare(
      Expression memberValue,
      ConstantExpression constant,
      FilterOperator op,
      bool isCaseSensitive )
    {
      if( op == FilterOperator.Equal )
      {
        return LinqExpressionBuilder.CompareEqual( memberValue, constant, isCaseSensitive );
      }
      else if( op == FilterOperator.NotEqual )
      {
        return LinqExpressionBuilder.CompareNotEqual( memberValue, constant, isCaseSensitive );
      }

      memberValue = LinqExpressionBuilder.ConvertToUnderlyingType( memberValue );

      Type memberValueType = memberValue.Type;
      Type constantType = constant.Type;

      // The values are of the same type.
      if( memberValueType == constantType )
      {
        return LinqExpressionBuilder.CompareValues( memberValue, constant, op, isCaseSensitive );
      }
      // Check if the constant can be converted to the left expression type.
      else if( ( memberValueType != typeof( object ) )
            && ( memberValueType.IsAssignableFrom( constantType ) ) )
      {
        constant = Expr.Constant( Convert.ChangeType( constant.Value, memberValueType, null ) );

        return LinqExpressionBuilder.Compare( memberValue, constant, op, isCaseSensitive );
      }
      // Try to use the IComparable.CompareTo method.
      else if( typeof( IComparable ).IsAssignableFrom( memberValueType ) )
      {
        MethodInfo methodInfo = memberValueType.GetMethod( "CompareTo", new Type[] { constantType } );

        if( methodInfo != null )
        {
          Type parameterType = methodInfo.GetParameters()[ 0 ].ParameterType;

          if( constantType != parameterType )
          {
            constant = Expr.Constant( constant.Value, parameterType );
          }

          memberValue = Expr.Call( memberValue, methodInfo, constant );
          constant = Expr.Constant( 0, memberValue.Type );

          // Retry the same method with the call to CompareTo.
          return LinqExpressionBuilder.Compare( memberValue, constant, op, isCaseSensitive );
        }
      }
      // Try to convert the left expression value to the right expression type.
      else if( ( memberValueType == typeof( object ) )
            && ( constantType != typeof( object ) ) )
      {
        memberValue = Expr.Convert( memberValue, constantType );

        return LinqExpressionBuilder.Compare( memberValue, constant, op, isCaseSensitive );
      }

      throw new InvalidOperationException( "Unable to compare the values." );
    }

    private static Expression CompareEqual( Expression expression, ConstantExpression constant )
    {
      return LinqExpressionBuilder.CompareEqual( expression, constant, true );
    }

    private static Expression CompareEqual(
      Expression memberValue,
      ConstantExpression constant,
      bool isCaseSensitive )
    {
      if( constant.Value == null )
        return LinqExpressionBuilder.CompareEqualNull( memberValue );

      memberValue = LinqExpressionBuilder.ConvertToUnderlyingType( memberValue );

      Type memberValueType = memberValue.Type;
      Type constantType = constant.Type;

      // The values are of the same type.
      if( memberValueType == constantType )
      {
        Expression value;

        // Manage to do a case insensitive comparision.
        if( ( typeof( string ) == constantType )
          && ( !isCaseSensitive ) )
        {
          MethodInfo toLowerMethodInfo = typeof( string ).GetMethod( "ToLower", new Type[ 0 ] );

          memberValue = Expr.Call( memberValue, toLowerMethodInfo );
          value = Expr.Call( constant, toLowerMethodInfo );
        }
        else
        {
          value = constant;
        }

        return Expr.Equal( memberValue, value );
      }
      // Check if the constant can be converted to the left expression type.
      else if( ( memberValueType != typeof( object ) )
            && ( memberValueType.IsAssignableFrom( constantType ) ) )
      {
        constant = Expr.Constant( Convert.ChangeType( constant.Value, memberValueType, null ) );

        return LinqExpressionBuilder.CompareEqual( memberValue, constant, isCaseSensitive );
      }
      // Try to convert the left expression value to the right expression type.
      else if( ( memberValueType == typeof( object ) )
            && ( constantType != typeof( object ) ) )
      {
        memberValue = Expr.Convert( memberValue, constantType );

        return LinqExpressionBuilder.CompareEqual( memberValue, constant, isCaseSensitive );
      }
      // Try using the Equals method.
      else
      {
        MethodInfo methodInfo = memberValueType.GetMethod( "Equals", new Type[] { constantType } );

        if( methodInfo != null )
        {
          Type parameterType = methodInfo.GetParameters()[ 0 ].ParameterType;
          if( constantType != parameterType )
          {
            constant = Expr.Constant( constant.Value, parameterType );
          }

          return Expr.Equal(
                   Expr.Call( memberValue, methodInfo, constant ),
                   Expr.Constant( true ) );
        }
      }

      throw new InvalidOperationException( "Unable to compare the values." );
    }

    private static Expression CompareNotEqual( Expression expression, ConstantExpression constant )
    {
      return LinqExpressionBuilder.CompareNotEqual( expression, constant, true );
    }

    private static Expression CompareNotEqual(
      Expression memberValue,
      ConstantExpression constant,
      bool isCaseSensitive )
    {
      if( constant.Value == null )
        return LinqExpressionBuilder.CompareNotEqualNull( memberValue );

      memberValue = LinqExpressionBuilder.ConvertToUnderlyingType( memberValue );

      Type memberValueType = memberValue.Type;
      Type constantType = constant.Type;

      // The values are of the same type.
      if( memberValueType == constantType )
      {
        Expression value;

        // Manage to do a case insensitive comparision.
        if( ( typeof( string ) == constantType )
          && ( !isCaseSensitive ) )
        {
          MethodInfo toLowerMethodInfo = typeof( string ).GetMethod( "ToLower", new Type[ 0 ] );

          memberValue = Expr.Call( memberValue, toLowerMethodInfo );
          value = Expr.Call( constant, toLowerMethodInfo );
        }
        else
        {
          value = constant;
        }

        return Expr.NotEqual( memberValue, value );
      }
      // Check if the constant can be converted to the left expression type.
      else if( ( memberValueType != typeof( object ) )
            && ( memberValueType.IsAssignableFrom( constantType ) ) )
      {
        constant = Expr.Constant( Convert.ChangeType( constant.Value, memberValueType, null ) );

        return LinqExpressionBuilder.CompareNotEqual( memberValue, constant, isCaseSensitive );
      }
      // Try to convert the left expression value to the right expression type.
      else if( ( memberValueType == typeof( object ) )
            && ( constantType != typeof( object ) ) )
      {
        memberValue = Expr.Convert( memberValue, constantType );

        return LinqExpressionBuilder.CompareNotEqual( memberValue, constant, isCaseSensitive );
      }
      // Try using the Equals method.
      else
      {
        MethodInfo methodInfo = memberValueType.GetMethod( "Equals", new Type[] { constantType } );

        if( methodInfo != null )
        {
          Type parameterType = methodInfo.GetParameters()[ 0 ].ParameterType;
          if( constantType != parameterType )
          {
            constant = Expr.Constant( constant.Value, parameterType );
          }

          return Expr.Equal(
                   Expr.Call( memberValue, methodInfo, constant ),
                   Expr.Constant( false ) );
        }
      }

      throw new InvalidOperationException( "Unable to compare the values." );
    }

    private static Expression CompareEqualNull( Expression expr )
    {
      return Expr.Equal( expr, Expr.Constant( null ) );
    }

    private static Expression CompareNotEqualNull( Expression expr )
    {
      return Expr.NotEqual( expr, Expr.Constant( null ) );
    }

    private static Expression CompareValues(
      Expression memberValue,
      ConstantExpression constant,
      FilterOperator op,
      bool isCaseSensitive )
    {
      Debug.Assert( memberValue.Type == constant.Type );

      Type dataType = memberValue.Type;

      if( ( op == FilterOperator.GreaterThan )
        || ( op == FilterOperator.GreaterThanOrEqual )
        || ( op == FilterOperator.LessThan )
        || ( op == FilterOperator.LessThanOrEqual ) )
      {
        // The string type must be compared using the string.Compare method.
        if( typeof( string ) == dataType )
        {
          // Manage to do a case insensitive comparision.
          Expression comparisonValue = constant;
          if( !isCaseSensitive )
          {
            MethodInfo toLowerMethodInfo = typeof( string ).GetMethod( "ToLower", new Type[ 0 ] );

            memberValue = Expr.Call( memberValue, toLowerMethodInfo );
            comparisonValue = Expr.Call( constant, toLowerMethodInfo );
          }

          MethodInfo methodInfo = typeof( string ).GetMethod( "Compare", new Type[] { dataType, dataType } );
          memberValue = Expr.Call( null, methodInfo, memberValue, comparisonValue );
          constant = Expr.Constant( 0, memberValue.Type );
        }
        // Try to use the IComparable.CompareTo method for types that doesn't have
        // the appropriate overloaded operators.  Primitive types doesn't need to
        // be checked since we already know they have those.
        else if( !dataType.IsPrimitive )
        {
          string operatorName;

          switch( op )
          {
            case FilterOperator.GreaterThan:
              operatorName = "op_GreaterThan";
              break;

            case FilterOperator.GreaterThanOrEqual:
              operatorName = "op_GreaterThanOrEqual";
              break;

            case FilterOperator.LessThan:
              operatorName = "op_LessThan";
              break;

            case FilterOperator.LessThanOrEqual:
              operatorName = "op_LessThanOrEqual";
              break;

            default:
              throw new InvalidOperationException( "Unable to create a comparable expression." );
          }

          MethodInfo methodInfo = dataType.GetMethod( operatorName, BindingFlags.Static | BindingFlags.Public );

          // Use the IComparable.CompareTo method for types that doesn't have the requested
          // comparison operation.
          if( ( methodInfo == null || !methodInfo.IsSpecialName )
            && ( typeof( IComparable ).IsAssignableFrom( dataType ) ) )
          {
            methodInfo = dataType.GetMethod( "CompareTo", new Type[] { dataType } );

            if( methodInfo != null )
            {
              Type parameterType = methodInfo.GetParameters()[ 0 ].ParameterType;

              if( dataType != parameterType )
              {
                constant = Expr.Constant( constant.Value, parameterType );
              }

              memberValue = Expr.Call( memberValue, methodInfo, constant );
              constant = Expr.Constant( 0, memberValue.Type );
            }
          }
        }

        switch( op )
        {
          case FilterOperator.GreaterThan:
            {
              return Expr.GreaterThan( memberValue, constant );
            }

          case FilterOperator.GreaterThanOrEqual:
            {
              return Expr.GreaterThanOrEqual( memberValue, constant );
            }

          case FilterOperator.LessThan:
            {
              return Expr.LessThan( memberValue, constant );
            }

          case FilterOperator.LessThanOrEqual:
            {
              return Expr.LessThanOrEqual( memberValue, constant );
            }

          default:
            throw new InvalidOperationException( "Unable to create a comparable expression." );
        }
      }
      else if( ( op == FilterOperator.Contains )
            || ( op == FilterOperator.ContainedIn )
            || ( op == FilterOperator.StartsWith )
            || ( op == FilterOperator.EndsWith ) )
      {
        // The operator is only supported on string data type. 
        if( typeof( string ) != dataType )
          throw new InvalidOperationException( "An attempt was made to use a filter operator that can only be applied to strings." );

        // Manage to do a case insensitive comparision.
        Expression comparisonValue = constant;
        if( !isCaseSensitive )
        {
          MethodInfo toLowerMethodInfo = typeof( string ).GetMethod( "ToLower", new Type[ 0 ] );

          memberValue = Expr.Call( memberValue, toLowerMethodInfo );
          comparisonValue = Expr.Call( constant, toLowerMethodInfo );
        }

        string operatorName;

        switch( op )
        {
          case FilterOperator.Contains:
            operatorName = "Contains";
            break;

          case FilterOperator.ContainedIn:
            {
              operatorName = "Contains";

              //Swap the left and right operand.
              Expression swap = memberValue;
              memberValue = comparisonValue;
              comparisonValue = swap;
            }
            break;

          case FilterOperator.StartsWith:
            operatorName = "StartsWith";
            break;

          case FilterOperator.EndsWith:
            operatorName = "EndsWith";
            break;

          default:
            throw new InvalidOperationException( "Unable to create a comparable expression." );
        }

        MethodInfo methodInfo = typeof( string ).GetMethod( operatorName, new Type[] { dataType } );

        return Expr.Equal(
                 Expr.Call( memberValue, methodInfo, comparisonValue ),
                 Expr.Constant( true ) );
      }

      throw new InvalidOperationException( "Unable to create a comparable expression." );
    }

    private static Expression ConvertToUnderlyingType( Expression expression )
    {
      // Take care of a Nullable<> type.
      if( expression.Type.IsNullableStruct() )
      {
        Type underlyingType = Nullable.GetUnderlyingType( expression.Type );
        expression = Expr.Convert( expression, underlyingType );
      }

      // Any enum type must be compared using it's underlying type.
      if( expression.Type.IsEnum )
      {
        Type underlyingType = Enum.GetUnderlyingType( expression.Type );
        expression = Expr.Convert( expression, underlyingType );
      }

      return expression;
    }

    private Expression GetItemMemberValue( string propertyName )
    {
      return m_getItemMemberValue.Invoke( m_parameter, propertyName );
    }

    #region Private Fields

    private FilterExpressionPreProcessor m_preProcessor;
    private FilterExpressionPreProcessorResult m_preProcessorResult;
    private Expression m_result; //null
    private ParameterExpression m_parameter;
    private Func<ParameterExpression, string, Expression> m_getItemMemberValue;

    #endregion
  }
}
